Ghi chú và tham khảo Tìm kiếm nhị phân

Ghi chú

  1. ↑ Bất cứ thuật toán tìm kiếm nào chỉ dựa trên các phép so sánh có thể được biểu diễn bằng cây so sánh nhị phân. Đường đi trong (internal path) là bất kỳ đường nào đi từ gốc tới một nút có sẵn. Gọi I {\displaystyle I} là độ dài đường đi trong (internal path length), hay tổng độ dài tất cả các đường đi trong của cây. Nếu mỗi phần tử có xác suất được tìm như nhau, trường hợp trung bình là 1 + I n {\displaystyle 1+{\frac {I}{n}}} , hoặc đơn giản hơn là một cộng với trung bình toàn bộ độ dài các đường đi trong trong cây. Nguyên nhân là do các đường đi trong biểu diễn các phần tử mà thuật toán tìm kiếm tiến hành so sánh với giá trị cần tìm. Độ dài của các đường này biểu diễn số phép lặp sau nút gốc. Làm phép cộng trung bình tổng độ dài các đường này với thêm một phép lặp nữa ở nút gốc sẽ ra trường hợp trung bình. Do đó, để giảm tối đa số phép so sánh trung bình, cần phải giảm độ dài đường đi trong I {\displaystyle I} . Thực chất cây biểu diễn tìm kiếm nhị phân đã giảm tối đa độ dài đường đi trong. Knuth 1998Lỗi harv: không có mục tiêu: CITEREFKnuth1998 (trợ giúp) chứng minh được rằng độ dài đường đi ngoài (external path - the path length over all nodes where both children are present for each already-existing node) được giảm tối đa khi các nút ngoài (các nút không có nút con) nằm trong hai bậc liên tiếp của cây. Điều này cũng áp dụng với các đường đi trong do độ dài đường đi trong I {\displaystyle I} có liên hệ tuyến tính với độ dài đường đi ngoài E {\displaystyle E} . Với mỗi cây có n {\displaystyle n} nút, I = E − 2 n {\displaystyle I=E-2n} . Khi mỗi cây con có số nút bằng nhau, tương đương với khi mảng được chia thành hai nửa ở mỗi phép lặp, các nút ngoài và các nút cha phía trong của chúng nằm trong vòng hai bậc. Như vậy, thuật toán tìm kiếm nhị phân đã giảm được tối đa số phép so sánh trung bình do cây so sánh của thuật toán này có độ dài đường trong nhỏ nhất.[12]
  2. ↑ Knuth 1998Lỗi harv: không có mục tiêu: CITEREFKnuth1998 (trợ giúp) cho thấy trên mẫu máy tính MIX của ông, được Knuth thiết kế để biểu diễn cho một chiếc máy tính thông thường, rằng thời gian chạy trung bình của cách làm này cho một lần tìm thành công là 17.5 log 2 ⁡ n + 17 {\textstyle 17.5\log _{2}n+17} đơn vị thời gian so với 18 log 2 ⁡ n − 16 {\textstyle 18\log _{2}n-16} đơn vị với tìm kiếm nhị phân thông thường. Độ phức tạp thời gian của cách làm này tăng nhẹ ở tốc độ chậm hơn, nhưng độ phức tạp ban đầu lớn hơn. [18]
  3. ↑ Knuth 1998Lỗi harv: không có mục tiêu: CITEREFKnuth1998 (trợ giúp) đã thực hiện phân tích hiệu suất thời gian của cả hai thuật toán tìm kiếm này. Trên chiếc máy tính MIX của Knuth, được ông thiết kế để biểu diễn cho một chiếc máy tính thông thường, tìm kiếm nhị phân trung bình mất 18 log ⁡ n − 16 {\textstyle 18\log n-16} đơn vị thời gian cho một lần tìm kiếm thành công, trong khi tìm kiếm tuyến tính khi có một sentinel node ở cuối danh sách mất 1.75 n + 8.5 − n  mod  2 4 n {\textstyle 1.75n+8.5-{\frac {n{\text{ mod }}2}{4n}}} đơn vị. Tìm kiếm tuyến tính có độ phức tạp ban đầu thấp hơn do nó chỉ yêu cầu các tính toán tối thiểu, nhưng sau đó nhanh chóng vượt qua tìm kiếm nhị phân về độ phức tạp. Trên máy tính MIX, binary search only outperforms linear search with a sentinel if n > 44 {\textstyle n>44} .[12][25]
  4. ↑ Inserting the values in sorted order or in an alternating lowest-highest key pattern will result in a binary search tree that maximizes the average and worst-case search time.[30]
  5. ↑ Một số cách triển khai bảng băm có thể thực hiện tìm kiếm với thời gian hằng số đảm bảo.[35]
  6. ↑ This is because simply setting all of the bits which the hash functions point to for a specific key can affect queries for other keys which have a common hash location for one or more of the functions.[40]
  7. ↑ Có một số bản cải thiện của bộ lọc Bloom giúp cải thiện độ phức tạp hoặc cho phép thao tác xóa; ví dụ, bộ lọc cuckoo sử dụng cách băm cuckoo nhằm những mục đích trên.[40]
  8. ↑ Tức là các mảng có độ dài 1, 3, 7, 15, 31...[61]

Chú thích

  1. ↑ Williams, Jr., Louis F. (ngày 22 tháng 4 năm 1976). A modification to the half-interval search (binary search) method. Proceedings of the 14th ACM Southeast Conference. ACM. tr. 95–101. doi:10.1145/503561.503582. Bản gốc lưu trữ ngày 12 tháng 3 năm 2017. Truy cập ngày 29 tháng 6 năm 2018.  Đã bỏ qua tham số không rõ |df= (trợ giúp); Đã bỏ qua tham số không rõ |url-status= (trợ giúp)
  2. ↑ Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Binary search".Lỗi sfn: không có mục tiêu: CITEREFKnuth1998 (trợ giúp)
  3. ↑ Butterfield & Ngondi 2016, tr. 46.Lỗi sfn: không có mục tiêu: CITEREFButterfieldNgondi2016 (trợ giúp)
  4. ↑ Cormen và đồng nghiệp 2009, tr. 39.Lỗi sfn: không có mục tiêu: CITEREFCormenLeisersonRivestStein2009 (trợ giúp)
  5. ↑ Weisstein, Eric W., "Binary search" từ MathWorld.
  6. 1 2 Flores, Ivan; Madpis, George (ngày 1 tháng 9 năm 1971). “Average binary search length for dense ordered lists”. Communications of the ACM 14 (9): 602–603. Bibcode:1985CACM...28...22S. ISSN 0001-0782. doi:10.1145/362663.362752. 
  7. 1 2 Knuth 1998, §6.2.1 ("Searching an ordered table"), phân mục "Algorithm B".Lỗi sfn: không có mục tiêu: CITEREFKnuth1998 (trợ giúp)
  8. ↑ Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Algorithm B".Lỗi sfn: không có mục tiêu: CITEREFKnuth1998 (trợ giúp)
  9. 1 2 3 Bottenbruch, Hermann (ngày 1 tháng 4 năm 1962). “Structure and use of ALGOL 60”. Journal of the ACM 9 (2): 161–221. ISSN 0004-5411. doi:10.1145/321119.321120.  Procedure is described at p. 214 (§43), titled "Program for Binary Search".
  10. 1 2 3 4 5 Knuth 1998, §6.2.1 ("Searching an ordered table"), phân mục "History and bibliography".Lỗi sfn: không có mục tiêu: CITEREFKnuth1998 (trợ giúp)
  11. 1 2 Kasahara & Morishita 2006, tr. 8–9.Lỗi sfn: không có mục tiêu: CITEREFKasaharaMorishita2006 (trợ giúp)
  12. 1 2 3 4 Knuth 1998, §6.2.1 ("Searching an ordered table"), phân mục "Further analysis of binary search".Lỗi sfn: không có mục tiêu: CITEREFKnuth1998 (trợ giúp)
  13. ↑ Knuth 1998, §6.2.1 ("Searching an ordered table"), "Theorem B".Lỗi sfn: không có mục tiêu: CITEREFKnuth1998 (trợ giúp)
  14. ↑ Chang 2003, tr. 169.Lỗi sfn: không có mục tiêu: CITEREFChang2003 (trợ giúp)
  15. 1 2 3 4 5 6 Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search".Lỗi sfn: không có mục tiêu: CITEREFKnuth1998 (trợ giúp)
  16. ↑ Shannon, Claude E. (tháng 7 năm 1948). “A Mathematical Theory of Communication”. Bell System Technical Journal 27 (3): 379–423. doi:10.1002/j.1538-7305.1948.tb01338.x.  Đã bỏ qua tham số không rõ |hdl= (trợ giúp)
  17. 1 2 3 Knuth 1997, §2.3.4.5 ("Path length").Lỗi sfn: không có mục tiêu: CITEREFKnuth1997 (trợ giúp)
  18. Knuth 1998, §6.2.1 ("Searching an ordered table"), phân mục "Exercise 23".Lỗi sfn: không có mục tiêu: CITEREFKnuth1998 (trợ giúp)
  19. ↑ Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Exercise 23".Lỗi sfn: không có mục tiêu: CITEREFKnuth1998 (trợ giúp)
  20. ↑ Rolfe, Timothy J. (1997). “Analytic derivation of comparisons in binary search”. ACM SIGNUM Newsletter 32 (4): 15–19. doi:10.1145/289251.289255. 
  21. ↑ Khuong, Paul-Virak; Morin, Pat. “Array Layouts for Comparison-Based Searching”. Journal of Experimental Algorithmics 22. Article 1.3. doi:10.1145/289251.289255. 
  22. ↑ Knuth 1997, §2.2.2 ("Sequential Allocation").Lỗi sfn: không có mục tiêu: CITEREFKnuth1997 (trợ giúp)
  23. 1 2 3 4 Beame, Paul; Fich, Faith E. (2001). “Optimal bounds for the predecessor problem and related problems”. Journal of Computer and System Sciences 65 (1): 38–72. doi:10.1006/jcss.2002.1822. 
  24. ↑ Sedgewick & Wayne 2011, §3.1, subsection "Rank and selection".Lỗi sfn: không có mục tiêu: CITEREFSedgewickWayne2011 (trợ giúp)
  25. Knuth 1998, Answers to Exercises (§6.2.1) cho "Exercise 5".Lỗi sfn: không có mục tiêu: CITEREFKnuth1998 (trợ giúp)
  26. ↑ Knuth 1998, §6.2.1 ("Searching an ordered table").Lỗi sfn: không có mục tiêu: CITEREFKnuth1998 (trợ giúp)
  27. ↑ Knuth 1998, §5.3.1 ("Minimum-Comparison sorting").Lỗi sfn: không có mục tiêu: CITEREFKnuth1998 (trợ giúp)
  28. ↑ Sedgewick & Wayne 2011, §3.2 ("Ordered symbol tables").Lỗi sfn: không có mục tiêu: CITEREFSedgewickWayne2011 (trợ giúp)
  29. ↑ Sedgewick & Wayne 2011, §3.2 ("Binary Search Trees"), subsection "Order-based methods and deletion".Lỗi sfn: không có mục tiêu: CITEREFSedgewickWayne2011 (trợ giúp)
  30. Knuth 1998, §6.2.2 ("Binary tree searching"), subsection "But what about the worst case?".Lỗi sfn: không có mục tiêu: CITEREFKnuth1998 (trợ giúp)
  31. ↑ Sedgewick & Wayne 2011, §3.5 ("Applications"), "Which symbol-table implementation should I use?".Lỗi sfn: không có mục tiêu: CITEREFSedgewickWayne2011 (trợ giúp)
  32. ↑ Knuth 1998, §5.4.9 ("Disks and Drums").Lỗi sfn: không có mục tiêu: CITEREFKnuth1998 (trợ giúp)
  33. ↑ Knuth 1998, §6.2.4 ("Multiway trees").Lỗi sfn: không có mục tiêu: CITEREFKnuth1998 (trợ giúp)
  34. ↑ Knuth 1998, §6.4 ("Hashing").Lỗi sfn: không có mục tiêu: CITEREFKnuth1998 (trợ giúp)
  35. Knuth 1998, §6.4 ("Hashing"), phân mục "History".Lỗi sfn: không có mục tiêu: CITEREFKnuth1998 (trợ giúp)
  36. ↑ Dietzfelbinger, Martin; Karlin, Anna; Mehlhorn, Kurt; Meyer auf der Heide, Friedhelm; Rohnert, Hans; Tarjan, Robert E. (tháng 8 năm 1994). “Dynamic perfect hashing: upper and lower bounds”. SIAM Journal on Computing 23 (4): 738–761. doi:10.1137/S0097539791194094. 
  37. ↑ Morin, Pat. “Hash tables” (PDF). tr. 1. Truy cập ngày 28 tháng 3 năm 2016. 
  38. ↑ Knuth 2011, §7.1.3 ("Bitwise Tricks and Techniques").Lỗi sfn: không có mục tiêu: CITEREFKnuth2011 (trợ giúp)
  39. 1 2 Silverstein, Alan, Judy IV shop manual (PDF), Hewlett-Packard, tr. 80–81 
  40. Fan, Bin; Andersen, Dave G.; Kaminsky, Michael; Mitzenmacher, Michael D. (2014). Cuckoo filter: practically better than Bloom. Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies. tr. 75–88. doi:10.1145/2674005.2674994. 
  41. ↑ Bloom, Burton H. (1970). “Space/time trade-offs in hash coding with allowable errors”. Communications of the ACM 13 (7): 422–426. Bibcode:1985CACM...28...22S. doi:10.1145/362686.362692.  Đã bỏ qua tham số không rõ |citeseerx= (trợ giúp); Đã bỏ qua tham số không rõ |df= (trợ giúp)
  42. ↑ Knuth 1998, §6.2.1 ("Searching an ordered table"), phân mục "An important variation".Lỗi sfn: không có mục tiêu: CITEREFKnuth1998 (trợ giúp)
  43. ↑ Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "Algorithm U".Lỗi sfn: không có mục tiêu: CITEREFKnuth1998 (trợ giúp)
  44. ↑ Moffat & Turpin 2002, tr. 33.Lỗi sfn: không có mục tiêu: CITEREFMoffatTurpin2002 (trợ giúp)
  45. 1 2 3 Knuth 1998, §6.2.1 ("Searching an ordered table"), phân mục "Interpolation search".Lỗi sfn: không có mục tiêu: CITEREFKnuth1998 (trợ giúp)
  46. ↑ Knuth 1998, §6.2.1 ("Searching an ordered table"), phân mục "Exercise 22".Lỗi sfn: không có mục tiêu: CITEREFKnuth1998 (trợ giúp)
  47. ↑ Perl, Yehoshua; Itai, Alon; Avni, Haim (1978). “Interpolation search—a log log n search”. Communications of the ACM 21 (7): 550–553. Bibcode:1985CACM...28...22S. doi:10.1145/359545.359557. 
  48. 1 2 3 Chazelle, Bernard; Liu, Ding (ngày 6 tháng 7 năm 2001). Lower bounds for intersection searching and fractional cascading in higher dimension. 33rd ACM Symposium on Theory of Computing. ACM. tr. 322–329. ISBN 978-1-58113-349-3. doi:10.1145/380752.380818. Truy cập ngày 30 tháng 6 năm 2018. 
  49. ↑ Chazelle, Bernard; Liu, Ding (ngày 1 tháng 3 năm 2004). “Lower bounds for intersection searching and fractional cascading in higher dimension” (PDF). Journal of Computer and System Sciences (bằng tiếng Anh) 68 (2): 269–284. ISSN 0022-0000. doi:10.1016/j.jcss.2003.07.003. Truy cập ngày 30 tháng 6 năm 2018.  Đã bỏ qua tham số không rõ |citeseerx= (trợ giúp)
  50. ↑ Emamjomeh-Zadeh, Ehsan; Kempe, David; Singhal, Vikrant (2016). Deterministic and probabilistic binary search in graphs. 48th ACM Symposium on Theory of Computing. tr. 519–532. arXiv:1503.00805. doi:10.1145/2897518.2897656. 
  51. ↑ Ben-Or, Michael; Hassidim, Avinatan (2008). “The Bayesian learner is optimal for noisy binary search (and pretty good for quantum as well)” (PDF). 49th Symposium on Foundations of Computer Science. tr. 221–230. ISBN 978-0-7695-3436-7. doi:10.1109/FOCS.2008.58. 
  52. ↑ Pelc, Andrzej (1989). “Searching with known error probability”. Theoretical Computer Science 63 (2): 185–202. doi:10.1016/0304-3975(89)90077-7. 
  53. ↑ Rivest, Ronald L.; Meyer, Albert R.; Kleitman, Daniel J.; Winklmann, K. Coping with errors in binary search procedures. 10th ACM Symposium on Theory of Computing. doi:10.1145/800133.804351. 
  54. ↑ Pelc, Andrzej (2002). “Searching games with errors—fifty years of coping with liars”. Theoretical Computer Science 270 (1–2): 71–109. doi:10.1016/S0304-3975(01)00303-6. 
  55. ↑ Rényi, Alfréd (1961). “On a problem in information theory”. Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei (bằng tiếng Hungarian) 6: 505–516. MR 0143666.  Bảo trì CS1: Ngôn ngữ không rõ (link)
  56. ↑ Høyer, Peter; Neerbek, Jan; Shi, Yaoyun (2002). “Quantum complexities of ordered searching, sorting, and element distinctness”. Algorithmica 34 (4): 429–448. arXiv:quant-ph/0102078. doi:10.1007/s00453-002-0976-3. 
  57. ↑ Childs, Andrew M.; Landahl, Andrew J.; Parrilo, Pablo A. (2007). “Quantum algorithms for the ordered search problem via semidefinite programming”. Physical Review A 75 (3). 032335. Bibcode:2007PhRvA..75c2335C. arXiv:quant-ph/0608161. doi:10.1103/PhysRevA.75.032335. 
  58. ↑ Grover, Lov K. (1996). A fast quantum mechanical algorithm for database search. 28th ACM Symposium on Theory of Computing. Philadelphia, PA. tr. 212–219. arXiv:quant-ph/9605043. doi:10.1145/237814.237866. 
  59. ↑ Knuth 1998, §6.2.1 ("Searching an ordered table"), subsection "History and bibliography".Lỗi sfn: không có mục tiêu: CITEREFKnuth1998 (trợ giúp)
  60. ↑ Peterson, William Wesley (1957). “Addressing for random-access storage”. IBM Journal of Research and Development 1 (2): 130–146. doi:10.1147/rd.12.0130. 
  61. "2n−1". OEIS A000225 Lưu trữ 2016-06-08 tại Wayback Machine. Truy cập ngày 7 tháng 5 năm 2016.
  62. ↑ Lehmer, Derrick (1960). Teaching combinatorial tricks to a computer. Proceedings of Symposia in Applied Mathematics 10: 180–181. doi:10.1090/psapm/010. 
  63. ↑ Chazelle, Bernard; Guibas, Leonidas J. (1986). “Fractional cascading: I. A data structuring technique” (PDF). Algorithmica 1 (1–4): 133–162. doi:10.1007/BF01840440.  Đã bỏ qua tham số không rõ |citeseerx= (trợ giúp)
  64. ↑ Chazelle, Bernard; Guibas, Leonidas J. (1986), “Fractional cascading: II. Applications” (PDF), Algorithmica 1 (1–4): 163–191, doi:10.1007/BF01840441 
  65. ↑ “bsearch – binary search a sorted table”. The Open Group Base Specifications (ấn bản 7). The Open Group. 2013. Bản gốc lưu trữ ngày 21 tháng 3 năm 2016. Truy cập ngày 28 tháng 3 năm 2016.  Đã bỏ qua tham số không rõ |url-status= (trợ giúp); Đã bỏ qua tham số không rõ |df= (trợ giúp)
  66. ↑ Stroustrup 2013, tr. 945.Lỗi sfn: không có mục tiêu: CITEREFStroustrup2013 (trợ giúp)
  67. ↑ Unisys (2012), COBOL ANSI-85 programming reference manual 1, tr. 598–601 
  68. ↑ “Package sort”. The Go Programming Language. Bản gốc lưu trữ ngày 25 tháng 4 năm 2016. Truy cập ngày 28 tháng 4 năm 2016.  Đã bỏ qua tham số không rõ |url-status= (trợ giúp); Đã bỏ qua tham số không rõ |df= (trợ giúp)
  69. ↑ “java.util.Arrays”. Java Platform Standard Edition 8 Documentation. Oracle Corporation. Bản gốc lưu trữ ngày 29 tháng 4 năm 2016. Truy cập ngày 1 tháng 5 năm 2016.  Đã bỏ qua tham số không rõ |url-status= (trợ giúp); Đã bỏ qua tham số không rõ |df= (trợ giúp)
  70. ↑ “java.util.Collections”. Java Platform Standard Edition 8 Documentation. Oracle Corporation. Bản gốc lưu trữ ngày 23 tháng 4 năm 2016. Truy cập ngày 1 tháng 5 năm 2016.  Đã bỏ qua tham số không rõ |url-status= (trợ giúp); Đã bỏ qua tham số không rõ |df= (trợ giúp)
  71. ↑ “List<T>.BinarySearch method (T)”. Microsoft Developer Network. Bản gốc lưu trữ ngày 7 tháng 5 năm 2016. Truy cập ngày 10 tháng 4 năm 2016.  Đã bỏ qua tham số không rõ |url-status= (trợ giúp); Đã bỏ qua tham số không rõ |df= (trợ giúp)
  72. ↑ “NSArray”. Mac Developer Library. Apple Inc. Bản gốc lưu trữ ngày 17 tháng 4 năm 2016. Truy cập ngày 1 tháng 5 năm 2016.  Đã bỏ qua tham số không rõ |url-status= (trợ giúp); Đã bỏ qua tham số không rõ |df= (trợ giúp)
  73. ↑ “CFArray”. Mac Developer Library. Apple Inc. Bản gốc lưu trữ ngày 20 tháng 4 năm 2016. Truy cập ngày 1 tháng 5 năm 2016.  Đã bỏ qua tham số không rõ |url-status= (trợ giúp); Đã bỏ qua tham số không rõ |df= (trợ giúp)
  74. ↑ “8.6. bisect — Array bisection algorithm”. The Python Standard Library. Python Software Foundation. Bản gốc lưu trữ ngày 25 tháng 3 năm 2018. Truy cập ngày 26 tháng 3 năm 2018.  Đã bỏ qua tham số không rõ |url-status= (trợ giúp); Đã bỏ qua tham số không rõ |df= (trợ giúp)
  75. ↑ Fitzgerald 2007, tr. 152.Lỗi sfn: không có mục tiêu: CITEREFFitzgerald2007 (trợ giúp)

Tài liệu

Tài liệu tham khảo

WikiPedia: Tìm kiếm nhị phân http://cglab.ca/~morin/teaching/5408/notes/hashing... http://mathworld.wolfram.com/.html http://adsabs.harvard.edu/abs/1985CACM...28...22S http://adsabs.harvard.edu/abs/2007PhRvA..75c2335C http://www2.lns.mit.edu/~avinatan/research/search-... http://algs4.cs.princeton.edu/home/ http://www.cs.princeton.edu/~chazelle/pubs/FClower... http://www.cs.princeton.edu/~chazelle/pubs/Fractio... http://www.cs.princeton.edu/~chazelle/pubs/Fractio... http://judy.sourceforge.net/doc/shop_interm.pdf